The present invention relates to cryptography, and more particularly to authentication, e.g. password authentication. In some embodiments, the invention allows establishment of a secure communication channel between two computer systems.
Consider two parties, Alice and Bob, who wish to use their respective computer systems 110, 120 (FIG. 1) to communicate securely over an insecure network 130. Suppose their only means of verifying each other's identity consists of a short secret password (e.g., a 4-digit PIN number π). In particular, neither of them knows a public key corresponding to the other party, and neither has a certified public key (i.e., a public key whose certificate can be verified by the other party). Here, Alice should be concerned not only with eavesdroppers, but also with the party with whom she is communicating since a priori she cannot even be certain that it is Bob. Bob's situation is similar.
If Alice and Bob shared a high-strength cryptographic key (i.e., a long secret), then this problem could be solved using standard solutions for setting up a secure channel (e.g., [4]; the bracketed numbers indicated references cited at the end of this disclosure before the claims). However, since Alice and Bob only share a short secret password, they must also be concerned with offline dictionary attacks. An offline dictionary attack occurs when an attacker obtains some information that can be used to perform offline verification of password guesses. We will call this password verification information. For a specific example, consider the following. Say Alice and Bob share a password π, and say an attacker somehow obtained a hash of the password h(π), where h is some common cryptographic hash function such as SHA-1 [40]. Then an attacker could go offline and run through a dictionary of possible passwords {π1, π2, . . . }, testing whether h(πi)=h(π). In general, the password verification information obtained by the attacker may not be as simple as a hash of a password, and an attacker may not always be able to test all possible passwords against the password verification information, but if he can test a significant number of passwords, this is still considered an offline dictionary attack. See Wu [46] for a fairly recent demonstration of how effective an offline dictionary attack can be.
Many common techniques for password authentication are unilateral authentication techniques—that is, only one party (a user or client 110 or 120) is authenticated to the other party (a server 120 or 110), but not vice-versa; they are also vulnerable to offline dictionary attacks or rely on certified (or otherwise authenticated) public keys.
The simplest password authentication technique is for the client to send a password to the server in the clear. This technique is used in some older Internet applications, as well as many web-based mail applications. Obviously this is insecure against an eavesdropper on the network, but is often considered acceptable on channels in which eavesdropping is relatively difficult.
A more advanced technique is challenge-response, in which the server sends a challenge to the client, and the client responds with a message depending on the challenge and the password, for instance the hash of the challenge and password concatenated. This type of authentication is used in some operating systems to enable network access. It is vulnerable to an offline dictionary attack by an eavesdropper since the challenge and its corresponding response, together, make password verification information.
A more secure technique sends a password to the server over an anonymous secure channel, in which the server has been verified using a public key. This type of authentication is used in some remote terminal applications, as well as web-based applications, and it depends intrinsically on the ability of the client to verify the server's public key (otherwise, an attacker can impersonate the server). When used on the web, the public key of the server is certified by a certification authority that is presumably trusted by the client. For remote terminal applications, there typically is no trusted third party, and security relies on the client recognizing the public key, perhaps with a “fingerprint,” or hash, of the public key.
PASSWORD AUTHENTICATED KEY EXCHANGE (PAKE). The purpose of PAKE is to provide mutual password authentication without pre-authenticated public keys and in such a way that the only feasible way to attack the protocol is to run a trivial online dictionary attack of simply iteratively guessing passwords and attempting to impersonate one of the parties. (Note that online attacks are easier to detect and thwart.) Using a PAKE protocol, the authenticating parties can “bootstrap” a short secret (the password) into a long secret (a cryptographic key) that thereafter can be used to provide a secure channel.
The problem of designing a secure PAKE protocol was proposed by Bellovin and Merritt [6] and by Gong et al. [25], and has since been studied extensively. Many PAKE protocols have been proposed, e.g., [7, 25, 24, 28, 29, 36, 44, 45, 33, 32], and many of these protocols have been shown to be insecure (see e.g., [41]). Recent protocols have proofs of security, based on certain well-known cryptographic assumptions, although some of these proofs assume the existence of ideal hash functions or ideal ciphers (i.e., black-box perfectly-random functions (random oracles) or keyed permutations, respectively). A few recent papers [2,10,1] present refinements of the EKE protocol of [7] and prove security based on the Diffie-Hellman (DH) assumption [19]. The first assumes both ideal ciphers and ideal hashes, while the others assume only ideal hashes. Other papers [37,47] present refinements of the OKE protocol of [36] and prove security based on the RSA assumption [43]. These all assume ideal hashes. Another paper [31] presents a new protocol based on a variant of the Cramer-Shoup cryptosystem [16] and proves security based on the decisional DH assumption (see, e.g., [8]), assuming only a public random string (not an ideal hash function). Some variants of the [31] protocol are presented in [21,30,13]. Another password-authenticated key exchange protocol was developed in [23] and proven secure based on trapdoor permutations without any setup assumptions, but with a restriction that concurrent sessions with the same password are prohibited.
Many existing techniques for designing efficient PAKE protocols can be viewed as variations of a small number of fundamental paradigms, and some of them are based on either the Diffie-Hellman or RSA assumptions. In particular, some existing techniques for designing efficient and provably secure PAKE protocols may be viewed as falling into one of the following two basic paradigms:                the password is used to encrypt some part of a message that is being used to perform key exchange, e.g., [1, 6, 10, 31, 37, 46, 47], or        the password is used to choose a parameter in a standard key exchange, e.g., [28, 32].        
Another approach to achieving PAKE is using oblivious polynomial evaluation (OPE), a primitive introduced by Naor and Pinkas [39]. OPE is a more general form of oblivious transfer (OT), first suggested by Rabin [42]. Goldreich and Lindell [23], following a suggestion of [39], showed that, by using OPE, one can achieve PAKE in the standard model using only trapdoor permutations. Although these are important theoretical contributions, the PAKE protocols based on OPE are not competitive with the most efficient PAKE protocols.